|
Because matrix multiplication is such a central operation in many numerical algorithms, much work has been invested in making matrix multiplication algorithms efficient. Applications of matrix multiplication in computational problems are found in many fields including scientific computing and pattern recognition and in seemingly unrelated problems such counting the paths through a graph.〔 Many different algorithms have been designed for multiplying matrices on different types of hardware, including parallel and distributed systems, where the computational work is spread over multiple processors (perhaps over a network). Directly applying the mathematical definition of matrix multiplication gives an algorithm that takes time on the order of to multiply two matrices ( in big O notation). Better asymptotic bounds on the time required to multiply matrices have been known since the work of Strassen in the 1960s, but it is still unknown what the optimal time is (i.e., what the complexity of the problem is). ==Iterative algorithm== The definition of matrix multiplication is that if for an matrix and an matrix , then is an matrix with entries :. From this, a simple algorithm can be constructed which loops over the indices from 1 through and from 1 through , computing the above using a nested loop: * Input: matrices and * Let be a new matrix of the appropriate size * For from 1 to : * * For from 1 to : * * * Let * * * For from 1 to : * * * * Set * * * Set * Return This algorithms takes time (in asymptotic notation).〔 A common simplification for the purpose of algorithms analysis is to assume that the inputs are all square matrices of size , in which case the running time is , i.e., cubic. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Matrix multiplication algorithm」の詳細全文を読む スポンサード リンク
|